package class_2;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
public class Coding_quickSort1 {
	public static void quickSort(int[] arr) {
		//处理特殊情况。
		if(arr==null || arr.length<2) {
			return ;
		}
		//主方法首次调用
		quick(arr,0, arr.length-1);
	}
	public static void quick(int[] arr, int l,int r) {
		//l==r, l>r直接返回， 不用处理。
		if(l>=r) {
			return ;
		}
		//随机取[l,r]的一个数nums[?]
		int x = arr[l+(int)(Math.random()*(r-l+1))];
		int pivot = partition(arr,l,r,x);
		quick(arr,l,pivot-1);
		quick(arr,pivot,r);
	}
	public static int partition(int[] arr,int l,int r,int x) {
		int i=l,xi=0;
		int a = i;
		//[l...a-1]为<=x的区间
		//[a...r]为>x的区间
		for(i=l;i<=r;i++) {
			if(arr[i]<=x) {
				//进行交换。
				swap(arr,a,i);
				if(arr[a]==x) {
					xi=a;//标记xi的坐标
				}
				a++;
			}
		}
		//将xi的元素作为分割点。
		swap(arr,a-1,xi);
		return a-1;
	}
	public static void swap(int[] arr,int i,int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	public static int MAX = 3000;
	public static void main(String[] args) {
		  Random random = new Random(100);
	        int[] arr = new int[MAX];
	        System.out.printf("输入规模:%d\n",MAX);
	        // 测试重复数字的情况
	        for (int i = 0; i < MAX; i++) {
	            arr[i] = random.nextInt(10000);
	        }
	        System.out.println("排序前:" + Arrays.toString(arr));
	        long startTime = System.nanoTime();
	        quickSort(arr);
	        long endTime = System.nanoTime();
	        System.out.println("排序后:" + Arrays.toString(arr));
	        System.out.println("出现重复数字的情况的执行时间: " + (endTime - startTime) + " 纳秒");

	        // 测试无重复数字的情况
	        random.setSeed(0);
	        Set<Integer> set = new HashSet<>();
	        while (set.size() < MAX) {
	            set.add(random.nextInt(10000));
	        }
	        int i = 0;
	        for (int x : set) {
	            arr[i++] = x;
	        }
	        System.out.println("--------------------------------");
	        System.out.println("排序前:" + Arrays.toString(arr));
	        startTime = System.nanoTime();
	        quickSort(arr);
	        endTime = System.nanoTime();
	        System.out.println("排序后:" + Arrays.toString(arr));
	        System.out.println("不出现重复数字的情况的执行时间: " + (endTime - startTime) + " 纳秒");

	        // 测试完全相同的情况
	        Arrays.fill(arr, 5);
	        System.out.println("--------------------------------");
	        System.out.println("排序前:" + Arrays.toString(arr));
	        startTime = System.nanoTime();
	        quickSort(arr);
	        endTime = System.nanoTime();
	        System.out.println("排序后:" + Arrays.toString(arr));
	        System.out.println("出现完全相同的重复数字的情况的执行时间: " + (endTime - startTime) + " 纳秒");
	        System.out.println("--------------------------------");
	}
}
